package com.hdu.point_offer;

import java.util.LinkedList;
import java.util.Queue;

public class lcr156 {


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) return "";
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            StringBuilder sb = new StringBuilder();
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (node == null) {
                    sb.append("null,");
                }
                else {
                    sb.append(node.val + ",");
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }
            return sb.substring(0, sb.length() - 1);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.equals("")) return null;
            String[] nodeStrs = data.split(",");
            TreeNode root = new TreeNode(Integer.parseInt(nodeStrs[0]));
            int index = 1;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (!nodeStrs[index].equals("null")) {
                    node.left = new TreeNode(Integer.parseInt(nodeStrs[index]));
                    queue.add(node.left);
                }
                index++;
                if (!nodeStrs[index].equals("null")) {
                    node.right = new TreeNode(Integer.parseInt(nodeStrs[index]));
                    queue.add(node.right);
                }
                index++;
            }
            return root;
        }
    }

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
}
